﻿//单词搜索(medium): https://leetcode.cn/problems/word-search/description/
class Solution {
public:
    //vector<vector<bool>> check(7,vector<bool>(7，false));
    int check[7][7];
    int n,m;
    bool exist(vector<vector<char>>& board, string word) {
        n=board.size(),m=board[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(board[i][j]==word[0]) 
                {
                    check[i][j]=1;                    
                    if(dfs(board,i,j,word,1))  return true;
                    //失败了，要恢复现场
                    check[i][j]=0;     
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board,int i,int j,string word,int pos)
    {
        if(pos==word.size())
        {
            return true;
        }
        int dx[4]={0,-1,0,1};
        int dy[4]={-1,0,1,0};
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k];    int y=j+dy[k];
            if(x>=0&&x<n &&y>=0&&y<m && board[x][y]==word[pos] && !check[x][y])
            {
                 check[x][y]=1;  
                if(dfs(board,x,y,word,pos+1))   return true;
                check[x][y]=0;  
            }
        }
        return false;
    }
};

//黄金矿工(medium): https://leetcode.cn/problems/path-with-maximum-gold/description/
class Solution {
public:
    int n,m;
    int sum;
    int GreatSum;
    bool check[16][16];
    int getMaximumGold(vector<vector<int>>& grid) {
        n=grid.size(),m=grid[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]>0)
                {
                    check[i][j]=true;
                    sum+=grid[i][j];
                    dfs(grid,i,j);
                    //恢复现场
                    check[i][j]=false;
                    sum-=grid[i][j];
                }
            }
        }
        return GreatSum;
    }

    int dx[4]={0,-1,0,1};
    int dy[4]={-1,0,1,0};
    void dfs(vector<vector<int>>& grid,int i,int j)
    {
        //int flag=0;
        if(GreatSum<sum)   GreatSum=sum;
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k];  int y=j+dy[k];
            if(x>=0&&x<n&&y>=0&&y<m && !check[x][y] && grid[x][y])
            {
                //int flag=1;
                sum+=grid[x][y];
                check[x][y]=true;
                dfs(grid,x,y);

                sum-=grid[x][y];
                check[x][y]=false;
            }
        }
        //if(flag==0&&GreatSum<sum)   GreatSum=sum;
    }
};
